package primaryAlgorithm.maxSubArray;
/**
 * @Date 2020/03/22
 * @author 王光浩
 * @Thinking 使用贪心方式（动态规划的一种）
 * @         思路解析：当我们使用暴力法来解决这个问题时，我们是通过获取所有可能的子序列组合，然后获取其中的
 * @         的最大值，但是这样出现了大量重复的比较和累加，所以我们需要进行优化，于是得到了现在的动态规划。
 */
public class MyMethodThree {
	 public int maxSubArray(int[] nums) {
		 int max=nums[nums.length-1];
		 for(int i=nums.length-2;i>=0;i--) {
			 nums[i]=Math.max(nums[i], nums[i]+nums[i+1]);
			 max=max<nums[i]?nums[i]:max;
		 }
		 return max;
	 }
	 /**
	  * @Date 2020/03/22
	  * @author 王光浩
	  * @Thinking nums[i]中存储以nums[i]结尾的最大子序列值。（正宗的动态规划）
	  */
	 public int maxSubArray2(int[] nums) {
		 int max=nums[0];
		 for(int i=1;i<nums.length;i++) {
			 nums[i]=Math.max(nums[i-1]+nums[i], nums[i]);  //关键在于这个公式
			 max=nums[i]>max?nums[i]:max;
		 }
		 return max;
	 }
}
